This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
3D models most widely used in various applications are those with a large number of small to medium sized connected components, each having up to a few hundred polygons on an average. This kind of models is called multi-connected or multi-component 3D models. They play an import role in fields as diverse as biology, physics, engineering and art. This kind of model can be used e.g. for mechanical CAD designs, architectural designs and chemical plants which are increasingly deployed in various virtual world applications.
Compact representation is one of the key issues for compact storage and efficient transmission. 3D models are usually represented by “indexed face set” that consists of a coordinate array and a face array. The coordinate array lists the coordinates of all vertices, and the face array lists each face by indexing its three vertices in the coordinate array. There is no compression involved in indexed face set. “Triangle strip”1 is a widely used compact representation of 3D models that is well supported by most graphic cards. The triangle strip method attempts to divide a 3D mesh into long strips of triangles, as shown in FIG. 1, and then encodes these strips. In FIG. 1, vertices v0, . . . , v7 define a strip of triangles, which are part of a 3D mesh model.
Most known 3D compression algorithms propose their own compact representation of 3D models to increase compression ratio. These compact representations work best for smooth surfaces with dense meshes of small triangles. However, large multi-connected 3D models have a large number of connected components, with small numbers of large triangles, often with arbitrary connectivity. The architectural and mechanical CAD models typically have many non-smooth surfaces making these methods less suitable. Moreover, most of the known approaches deal with each connected component separately. Thus, such representations of 3D models do not perform well on large multi-component 3D models.
Recently, some compact representations specially designed for large multi-component 3D models have been proposed. [CAI09VRST]2 and [CAI09VRCAI]3 proposed a compact representation method for large multi-component 3D models, and can detect repeating instances regardless of rotation, translation and/or scaling. Further, displacement maps have been described e.g. in [SKU2008]4 for defining surface details of 3D mesh models. Such details are called mesostructures (as opposed to macrostructures, which define the shape of objects), and include high frequency geometric details that provide textures or light effects. Thus, they are relatively small but still visible, such as bumps on a surface.